package code.oldCode.feishuSpecializedTraining.dynamic;

import java.util.Arrays;

public class MyDP3 {
    // 1049. 最后一块石头的重量 II
    public int lastStoneWeightII(int[] stones) {
        // 背包物品为stones[],背包大小为总和的一半
        // 求不超过背包大小,能拿的最大值
        // 物品不可复选,无顺序
        int len = stones.length;
        int sum = Arrays.stream(stones).sum();
        int backpack_size = sum / 2;
        // dp[i][j]表示前i个物品,背包大小为j,最多能拿多少
        int[][] dp = new int[len + 1][backpack_size + 1];
        // 外层遍历物品
        for (int i = 1; i <= len; i++) {
            int nowItem = stones[i - 1];
            // 内层遍历背包大小
            for (int j = 1; j <= backpack_size; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nowItem)
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - nowItem] + nowItem);
            }
        }
        return sum - 2 * dp[len][backpack_size];
    }

    // 494. 目标和
    private int ways = 0;

    public int findTargetSumWays(int[] nums, int target) {
        // 1 <= nums.length <= 20
        // 尝试回溯，但是时间很慢，或许需要DP
        int len = nums.length;
        findBackTrace(nums, target, 0, 0);
        return ways;
    }

    private void findBackTrace(int[] nums, int target, int index, int sum) {
        if (sum == target && index == nums.length) {
            ways++;
            return;
        }
        if (index == nums.length)
            return;
        findBackTrace(nums, target, index + 1, sum + nums[index]);
        findBackTrace(nums, target, index + 1, sum - nums[index]);
    }

    public int findTargetSumWays_dp(int[] nums, int target) {
        // 尝试DP
        // 0 <= sum(nums[i]) <= 1000 说明怎么求和正负都不超过[-1000,1000]
        // 背包为nums，大小为target，但是可以暂时超过背包大小？！求拿到target的选取方式的数量。
        int len = nums.length;
        // dp[i][j+1000]表示前i个物品（全选）最终目标和为j的选取方式的数量
        int[][] dp = new int[len][2001];
        // 这里用+=是因为tm的nums=[0]且target=0的情况下有0和-0两种情况
        dp[0][nums[0] + 1000] += 1;
        dp[0][-nums[0] + 1000] += 1;
        // dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
        for (int i = 1; i < len; i++) {
            // 这里不同于传统背包遍历到target就行，而是全部大小都遍历，因为允许暂时超过背包大小
            for (int j = 0; j <= 2000; j++) {
                int positive = nums[i], negative = -nums[i];
                // 正（反）选时，当在范围内，就加上i-1的和为j-positive(negative)的情况
                if (j - positive >= 0 && j - positive <= 2000)
                    dp[i][j] += dp[i - 1][j - positive];
                if (j - negative >= 0 && j - negative <= 2000)
                    dp[i][j] += dp[i - 1][j - negative];
            }
        }
        return dp[len - 1][target + 1000];
    }

    public int findTargetSumWays_dp2(int[] nums, int target) {
        // 官解下的回答：背包元素分为选正和选负两组 0 <= nums[i] <= 1000
        // pos + neg = sum
        // pos - neg = target
        // so, pos = (sum + target) / 2, ※问题转化为找nums中选和为pos的子物品的数量！
        // dp[i][j]表示前i个里选择（可选可不选），和为j的选择方式的个数
        int len = nums.length;
        int sum = Arrays.stream(nums).sum();
        if ((sum + target) % 2 == 1 || sum + target < 0) // ※如果为奇数或负数，则无解
            return 0;
        int newTarget = (sum + target) / 2;
        int[][] dp = new int[len][newTarget + 1];
        if (nums[0] <= newTarget)
            dp[0][nums[0]] += 1;
        dp[0][0] += 1; // ※前1个，和为0，不选的情况
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= newTarget; j++) {
                // dp[i][j] = 选它dp[i-1][j-nums[i]] + 不选它dp[i-1][j]
                if (j - nums[i] >= 0)
                    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[len - 1][newTarget];
    }

    // 474. 一和零
    public int findMaxForm(String[] strs, int m, int n) {
        // 背包问题，不可重复选，求不大于背包的最大选取物品数
        int len = strs.length;
        // dp[i][j][k]表示前i个str满足0不超过m和1不超过n的最大子集数
        int[][][] dp = new int[len][m + 1][n + 1];
        // dp[i][j][k] = Max(dp[i-1][j-0的个数][K-1的个数]，dp[i-1][j][k])
        // 初始化，选前0个str
        int[] nums01 = get01Num(strs[0]);
        for (int j = 0; j <= m; j++) {
            if (nums01[0] > j)
                continue;
            for (int k = 0; k <= n; k++) {
                if (nums01[1] > k)
                    continue;
                dp[0][j][k] = 1;
            }
        }
        for (int i = 1; i < len; i++) {
            int[] nums = get01Num(strs[i]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    // 可选
                    if (nums[0] <= j && nums[1] <= k) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - nums[0]][k - nums[1]] + 1);
                    }
                }
            }
        }
        return dp[len - 1][m][n];
    }

    private int[] get01Num(String str) {
        int[] nums = new int[2];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '0')
                nums[0]++;
            else if (c == '1')
                nums[1]++;
        }
        return nums;
    }

    public static void main(String[] args) {
        MyDP3 m = new MyDP3();
        String[] strs = {"10","0001","111001","1","0"};
        System.out.println(m.findMaxForm(strs, 5, 3));
    }
}
